"""


快排的算法思想：选择一个基准元素，通过一趟排序将数组分为两部分，左部分元素均小于基准，右部分元素均大于基准；然后递归对两部分进行快速排序。

代码解释：
quick_sort函数为递归入口，通过partition函数将数组分区后递归处理左右子数组。
partition函数逻辑：
    选择最左元素作为基准pivot。
    右指针right左移找小于pivot的元素，放到左指针位置。
    左指针left右移找大于pivot的元素，放到右指针位置。
    重复上述步骤直到left == right，将pivot放到该位置，返回基准索引。
时间复杂度：最好情况和平均情况为O(nlogn)，最坏情况（有序）为O(n²)。


以数字 [5, 2, 9, 1, 6, 3] 为例，演示快速排序的过程（选择第一个元素 5 作为基准 "基准值"）：
步骤 1：第一次分区（以 5 为基准）
    目标：将小于 5 的数放左边，大于 5 的数放右边。
    初始数组：[5, 2, 9, 1, 6, 3]
    遍历比较：
        2 < 5 → 放左边 → 临时数组：[2, ...]
        9 > 5 → 放右边 → 临时数组：[2, ..., 9]
        1 < 5 → 放左边 → 临时数组：[2, 1, ..., 9]
        6 > 5 → 放右边 → 临时数组：[2, 1, ..., 9, 6]
        3 < 5 → 放左边 → 临时数组：[2, 1, 3, 5, 9, 6]
    分区结果：[2, 1, 3] + [5] + [9, 6]（基准值 5 已归位）

步骤 2：递归处理左分区 [2, 1, 3]（选 2 为基准）
目标：将小于 2 的数放左边，大于 2 的数放右边。
遍历比较：
    1 < 2 → 放左边 → [1, ...]
    3 > 2 → 放右边 → [1, 2, 3]
分区结果：[1] + [2] + [3]（基准值 2 已归位，左右子分区长度为 1，无需再分）

步骤 3：递归处理右分区 [9, 6]（选 9 为基准）
目标：将小于 9 的数放左边，大于 9 的数放右边。
遍历比较：
    6 < 9 → 放左边 → [6, 9]
分区结果：[6] + [9]（基准值 9 已归位，左右子分区长度为 1，无需再分）

最终排序结果
将所有分区合并：[1, 2, 3, 5, 6, 9]
核心逻辑：通过 "基准值分区" 将数组拆分为左右两部分，再递归处理子分区，直到所有元素归位。


"""


def quick_sort(arr, low, high):
    # 递归终止条件：子数组长度为0或1
    if low < high:
        # 分区操作，返回基准元素的最终位置
        pivot_pos = partition(arr, low, high)
        # 递归排序左子数组
        quick_sort(arr, low, pivot_pos - 1)
        # 递归排序右子数组
        quick_sort(arr, pivot_pos + 1, high)
    return arr


def partition(arr, low, high):
    # 选择最左元素作为基准
    pivot = arr[low]
    # 左右指针
    left = low
    right = high
    # 循环直到左右指针相遇
    while left < right:
        # 右指针左移，找小于基准的元素
        while left < right and arr[right] >= pivot:
            right -= 1
        # 将找到的元素放到左指针位置 如果存在需要"复制"过去的情景，因为第一个基准元素早就被提前记录好了(pivot值) 所以不用担心被覆盖导致找不到该值了
        arr[left] = arr[right]
        # 左指针右移，找大于基准的元素
        while left < right and arr[left] <= pivot:
            left += 1
        # 将找到的元素放到右指针位置
        arr[right] = arr[left]
    # 将基准元素放到最终位置  最后一定是left的索引位置来放基准值
    arr[left] = pivot
    # 返回基准位置
    return left

# 测试
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
sorted_arr = quick_sort(arr, 0, n - 1)
print("快速排序结果:", sorted_arr)
